package com.gitee.feizns.explore.data_structure.union_find;

/**
 * @author feizns
 * @since 2020/3/11
 */
public class QuickUnion implements UnionFind {

    private int[] parent;

    public QuickUnion(int size) {
        this.parent = new int[size];
        for (int i = 0; i < parent.length; i++)
            parent[i] = i;
    }

    @Override
    public int size() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if ( i != j )
            parent[i] = j;
    }

    private int find(int p) {
        int t = p;
        while ( t != parent[t] )
            t = parent[t];
        return t;
    }

    public static void main(String[] args) {
        QuickUnion union = new QuickUnion(20);
        System.out.println(union.isConnected(0, 19));
        union.union(0, 19);
        System.out.println(union.isConnected(0, 19));
        union.union(2, 0);
        System.out.println(union.isConnected(2, 19));
        System.out.println(union.isConnected(3, 19));
    }

}
